#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, SQRTN = 700;
int a[N];
struct BLOCK {
    int lmt;
    int block;
    int tot;
    int sum1[N];
    int sum2[SQRTN];
    int bl[N];
    void init(int n) {
        lmt = n;
        block = sqrt(n);
        tot = n / block + (n % block != 0);
        for (int i = 1; i <= tot; i++) {
            int lp = (i - 1) * block + 1, rp = min(n, block * i);
            for (int j = lp; j <= rp; j++) {
                bl[j] = i;
            }
        }
    }
    void update(int x, int v) {
        int p = bl[x];
        int lp = (p - 1) * block + 1;
        for (int i = x; i >= lp; i--) {
            sum1[i] += v;
        }
        for (int i = p - 1; i >= 1; i--) {
            sum2[i] += v;
        }
    }
    inline int query(int x) {
        int p = bl[x];
        return sum2[p] + sum1[x];
    }
} vb;
int ac[N];
int ql[N], qr[N], qidx[N];
int bl[N];
int block;
int tot;
bool cmp(int x, int y) { return bl[ql[x]] < bl[ql[y]] || bl[ql[x]] == bl[ql[y]] && qr[x] < qr[y]; }
struct command {
    int p, val, w;
};
vector<command> times[N];
long long ans[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ac[i] = a[i];
    }
    sort(ac + 1, ac + 1 + n);
    int ncnt = unique(ac + 1, ac + 1 + n) - ac - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(ac + 1, ac + 1 + ncnt, a[i]) - ac;
    }
    vb.init(ncnt + 1);
    for (int i = 1; i <= m; i++) {
        cin >> ql[i] >> qr[i];
        qidx[i] = i;
    }
    block = sqrt(n);
    tot = n / block + (n % block != 0);
    for (int j = 1; j <= tot; j++) {
        int lp = (j - 1) * block + 1, rp = min(j * block, n);
        for (int i = lp; i <= rp; i++) {
            bl[i] = j;
        }
    }
    sort(qidx + 1, qidx + 1 + m, cmp);
    int cl = 1, cr = 0;
    for (int p = 1; p <= m; p++) {
        int l = ql[qidx[p]], r = qr[qidx[p]];
        while (cr < r) {
            cr++;
            times[cl - 1].push_back({ qidx[p], a[cr] + 1, -1 });
            times[cr - 1].push_back({ qidx[p], a[cr] + 1, 1 });
        }
        while (cr > r) {
            times[cl - 1].push_back({ qidx[p], a[cr] + 1, 1 });
            times[cr - 1].push_back({ qidx[p], a[cr] + 1, -1 });

            cr--;
        }
        while (cl < l) {
            times[cl].push_back({ qidx[p], a[cl], -1 });
            times[cr].push_back({ qidx[p], a[cl], 1 });
            ans[qidx[p]] -= cr - cl;

            cl++;
        }
        while (cl > l) {
            cl--;
            times[cl].push_back({ qidx[p], a[cl], 1 });
            times[cr].push_back({ qidx[p], a[cl], -1 });
            ans[qidx[p]] += cr - cl;
        }
    }
    for (int i = 1; i <= n; i++) {
        vb.update(a[i], 1);
        for (command c : times[i]) {
            ans[c.p] += vb.query(c.val) * c.w;
        }
    }
    for (int i = 1; i <= m; i++) {
        ans[qidx[i]] += ans[qidx[i - 1]];
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
}